The present invention generally relates to wireless communication and, more particularly, to a distributed medium access protocol for wireless mesh networks.
Recently, multi-hop wireless networks and proprietary commercial systems have focused on a class of networks termed “mesh networks”. Unlike mobile ad hoc networks (“MANETs”), in which communication generally occurs between any pair of nodes through several mobile relaying nodes, wireless mesh networks (“WMNs”) serve as access networks utilizing non-mobile relaying nodes to provide wireless backbone services for nomadic users to access the wired Internet. In such an environment, it is essential for all nodes to support quality-of-service (QoS) transport in multi-hop operation under a highly loaded situation. However, it has been found difficult to fulfill the above-mentioned requirements using the standard 802.11 distributed coordination function (“DCF”). It has also been found that ready-to-send/clear-to-send (RTS/CTS) does not efficiently schedule transmissions, and therefore fails to obtain a good schedule in a multi-hop chain. Although techniques such as multi-channel, spatial-reuse, cut-through, or enhanced physical carrier sensing may improve the performance of 802.11 DCF, these techniques still rely on the random-access-based carrier sense multiple access with collision avoidance (“CSMA/CA”) mechanism and thus, suffer from the same fairness problems, backoff inefficiencies, and unavoidable high collision rate problems under a highly loaded environment. These problems are schematically illustrated and discussed below.
FIG. 1 is a schematic diagram illustrating hidden and exposed nodes in a network. A hidden-node problem refers to collisions of packets at a receiver node due to simultaneous transmission at different nodes, which are not within the direct transmission range of a sender but are within the transmission range of the receiver. Referring to FIG. 1, a first sender node S1 having a transmission range TR1 and a second sender node S2 having a transmission range TR2 are hidden from one another when both attempt to send packets to a first receiver node R1 located within the transmission ranges TR1 and TR2. A collision occurs when both sender nodes S1 and S2 transmit at the same time without knowing about the transmission of one another. It is difficult for a sender node to detect the existence of hidden nodes because the sender node is not able to sense transmission from the hidden nodes.
An exposed-node problem refers to the inability of a sender node, which is blocked due to a nearby sender node, to transmit packets to a receiver node. Referring again to FIG. 1, a third sender node S3, exposed to the transmission range TR1 of first node S1, is prohibited from transmitting packets to a second receiver node R2 when first node S1 is transmitting packets to first receiver node R1. However, third sender node S3 should be able to transmit packets to second receiver node R2 without incurring any collision when first sender node S1 is transmitting packets to first receiver node R1. It is also difficult for a sender node to detect exposed nodes because the sender node is not able to sense transmission from the exposed nodes.
FIGS. 2A and 2B are schematic diagrams illustrating hidden and exposed nodes in a mesh network. FIG. 2A illustrates a hidden-node problem in the mesh network. Referring to FIG. 2A, the mesh network includes nodes A, B, C and D, which transmit and receive signals in a same radio channel. When data packets are to be sent from node A to node B, node A broadcasts a ready-to-send (RTS) frame in its transmission range. Node B, located within the transmission range of node A, receives the RTS frame and transmits a clear-to-send (CTS) frame to node A, which does not send the data packets until the CTS frame sent from node B is received. When node B broadcasts the CTS frame, node D broadcasts another RTS frame denoted as RTS1 to node C. Node C, located within the transmission ranges of node B and node D, simultaneously receives the CTS and RTS1 frames, resulting in a collision. Node D, having not received any CTS frame from node C over a period of time, broadcasts still another RTS frame denoted as RTS2. However, when node C transmits a CTS frame in the radio channel in response to the RTS2 frame, a collision occurs at node B, which receives data packets from node A while overhearing the CTS frame sent from node C.
FIG. 2B illustrates an exposed-node problem in the mesh network. Referring to FIG. 2B, node B transmits a CTS frame in response to an RTS frame sent from node A. Node C, overhearing the CTS frame, is prohibited from transmitting an RTS frame. Node C must wait for a period of time, i.e., backoff, before it can transmit an RTS frame. The backoff is undesired and may often adversely affect the overall system performance of the mesh network.
FIG. 3A is a schematic diagram illustrating multihop packet forwarding in a network system using 802.11 DCF, which has been disclosed in a paper entitled “Multihop Connections Using 802.11” Hiertz et al. Referring to FIG. 3A, unidirectional multihop packets are forwarded along a long chain of nodes. In this chain model, all packets are originated at a first node and are hop-by-hop forwarded to a last node in the chain. The multihop packet forwarding uses 802.11 DCF, which is based on the CSMA/CA mechanism adopted by IEEE 802.11 medium access control (“MAC”). In the example, a packet 2 forwarded by a node n+1 is affected by a packet 1 being forwarded by a node n+3. It has been found that the maximum utilization of a chain using 802.11 with RTS/CTS can only approach 1/7. However, a desirable utilization of a long chain of nodes in isolation should be ¼ or even ⅓, depending on the spatial reuse distance of the raw channel bandwidth of the radio if an ideal MAC protocol is adopted.
FIG. 3B is a schematic diagram illustrating multihop packet forwarding in a network system using an ideal MAC protocol. Referring to FIG. 3B, with the ideal MAC protocol, two nodes separated by a spatial reuse distance are able to send at the same time without affecting each other. Under this ideal condition, data packets are forwarded hop-by-hop like ripples of water moving apart from a central location. To activate this “ripple phenomenon,” each node needs to know the optimum duration between every two consecutive packet transmissions. For example, a node n+1, instead of a node n itself, can determine the optimal duration for the node n by overhearing an RTS frame transmitted by a node n+2. Consequently, the node n+1 may notify the node n to send a next packet at the end of the node n+2's transmission.
A complete solution to the hidden and exposed problems requires centralized and global knowledge among all mesh nodes. Such a solution would require extensive monitoring and management overhead. It is therefore desirable to have a distributed solution that approximates the complete solution based on limited information exchange among nodes in order to improve the throughput and quality of service (QoS) of a WMN and enhance the equity in accessing the wireless medium of a WMN.